package oj;

public class LC1201 {
    public int nthUglyNumber(int n, int a, int b, int c) {
            long ab=lcm(a,b);
            long ac=lcm(a,c);
            long bc=lcm(b,c);
            long abc=lcm(ab,c);
            int min=Math.min(a,Math.min(b,c));
            int left=min;
            int right=min*n;
            while(left<=right){
                int mid=right-(right-left)/2;
                long count=mid/a+mid/b+mid/c-mid/ab-mid/ac-mid/bc+mid/abc;
                if(count<n){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            return (int)left;
        }
        private static long lcm(long x,long y){
            return x*y/gcd(x,y);
        }
        private static long gcd(long x,long y){
            return x==0?y:gcd(y%x,x);
        }
    }